//
//  main.cpp
//  17.电话号码的字母组合
//
//  Created by Yan Zihao on 2024/10/14.
//

#include <iostream>
#include <vector>
using namespace std;

/*
*思路：这里有一篇比较好的图文并貌的博客，大家参考可能会更容易理解，故贴出链接
https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/solution/tong-su-yi-dong-dong-hua-yan-shi-17-dian-hua-hao-m/
*/
class Solution {
public:
  void func(vector<string> &res, string str, string &digits, unordered_map<char, string> &m, int k)
  {
    if(str.size() == digits.size())
    {
      res.push_back(str);
      return;
    }
    string tmp = m[digits[k]];
    for(char w : tmp)
    {
      str += w;
      func(res, str, digits, m, k+1);
      str.pop_back();
    }
    return ;
  }

  vector<string> letterCombinations(string digits) {
    unordered_map<char, string> table
    {
      {'0', " "}, {'1',"*"}, {'2', "abc"},
      {'3',"def"}, {'4',"ghi"}, {'5',"jkl"},
      {'6',"mno"}, {'7',"pqrs"},{'8',"tuv"},
      {'9',"wxyz"}};
    vector<string> res;
    if(digits == "")
      return res;
    func(res, "", digits, table, 0);
    return res;
  }
};
